//289. 生命游戏
//根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
//
//给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
//
//如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
//如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
//如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
//如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
//根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
//
//
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/game-of-life

package game_of_life

// getRound 获取周围格子信息
// x 对应 height
// y 对应 width
func getRound(board [][]int, x, y int) (res []int) {
	h := len(board)
	w := len(board[0])
	u, d, l, r := y-1, y+1, x-1, x+1 // 设置四个边界

	// 进行合法边界判断
	// 不合法则等同于边界

	if u < 0 {
		u = y
	}

	if l < 0 {
		l = x
	}

	if d >= w {
		d = y
	}

	if r >= h {
		r = x
	}

	for i := u; i <= d; i++ {
		for j := l; j <= r; j++ {
			// 跳过自身
			if i == y && j == x {
				continue
			}
			res = append(res, board[j][i])
		}
	}
	return
}

// sum 数组求和
func sum(nums []int) int {
	res := 0
	for _, n := range nums {
		res += n
	}
	return res
}

// stateMachine 状态机
// state 对应本身状态
// x 对应 height
// y 对应 width
func stateMachine(board [][]int, state, x, y int) int {
	alive := sum(getRound(board, x, y))
	if state == 1 {
		if 3 < alive || alive < 2 {
			return 0
		} else {
			return 1
		}
	} else {
		if alive == 3 {
			return 1
		} else {
			return 0
		}
	}
}

// getNextLife 获取下一生命状态
func getNextLife(board [][]int) [][]int {
	h := len(board)
	w := len(board[0])
	res := make([][]int, h)

	for i := 0; i < h; i++ {
		res[i] = make([]int, w)
	}

	for i, item := range board {
		for j, v := range item {
			res[i][j] = stateMachine(board, v, i, j)
		}
	}

	// 最后修改board
	return res
}

func gameOfLife(board [][]int) {
	for i, item := range getNextLife(board) {
		for j, v := range item {
			board[i][j] = v
		}
	}
}
